% Copyright (C) 2017 Koz Ross <koz.ross@retro-freedom.nz>

% This work is licensed under the Creative Commons Attribution-ShareAlike 4.0 
% International License. To view a copy of this license, visit 
% http://creativecommons.org/licenses/by-sa/4.0/ or send a letter to Creative 
% Commons, PO Box 1866, Mountain View, CA 94042, USA.

\documentclass{beamer}

\usepackage[utf8]{inputenc}
\usecolortheme{seahorse}
\usefonttheme{professionalfonts}
\usepackage{fontspec}
\setmainfont{DejaVu Sans}
\setbeamertemplate{navigation symbols}{}
\usepackage{caption}
\usepackage[font=itshape, begintext=``, endtext='']{quoting}
\usepackage{fancyvrb}
\usepackage{color}

\title{Recursion schemes}
\subtitle{Or: why your abstractions are {\em still\/} weak}
\titlegraphic{\includegraphics[scale=0.8]{img/logo.pdf}}
\author{Koz Ross}
\date{17th August, 2017}

\begin{document}

\begin{frame}[c]
  \titlepage{}
\end{frame}

\begin{frame}[c]
  \frametitle{Outline}
  \tableofcontents
\end{frame}

\section{Introduction}

\begin{frame}[c, fragile]
  \frametitle{How many of you felt after the functor talk}
  \begin{center}
    \includegraphics[scale=0.35]{img/how-do-i-used-functor.pdf}\pause{}

    Let me show you!
  \end{center}
\end{frame}

\section{Preliminaries}

\begin{frame}[c, fragile]
  \frametitle{Recursive data types}

  We can express certain structures in a recursive manner:\pause{}

  \begin{Verbatim}[commandchars=\\\{\}]
  data List a = 
    Nil | \color{gray}-- base case
    Cons a (List a) \color{gray}-- inductive case
  \end{Verbatim}
  \pause{}

  Under this definition, we get the following `expansions':\pause{}

  \begin{Verbatim}[commandchars=\\\{\}]
  [] == Nil \color{gray}-- obviously
  [1] == Cons 1 Nil
  [1, 2, 3] == Cons 1 (Cons 2 (Cons 3 Nil))
  \color{gray}-- and so on\ldots
  \end{Verbatim}
  \pause{}

  As long as we `bottom out' somewhere, this is fine. It also allows us to write
  very elegant code for processing such data structures.
\end{frame}

\begin{frame}[c, fragile]
  \frametitle{How to use recursive data types}
  \pause{}
  \begin{Verbatim}[commandchars=\\\{\}]
  instance Functor List where
    map f Nil = Nil
    map f Cons head tail = Cons (f head) (map f tail)
  \end{Verbatim}
  \pause{}

  This would lead to the following `expansion':\pause{}

  \begin{Verbatim}[commandchars=\\\{\}]
  \color{gray}-- this expression
  map inc [1, 2, 3] \color{gray}-- Cons 1 (Cons 2 (Cons 3 Nil))
  \color{gray}-- would be evaluated like this\pause{}
  Cons (inc 1) (map inc [2, 3])\pause{}
  Cons (inc 1) (Cons (inc 2) (map inc [3]))\pause{}
  Cons (inc 1) (Cons (inc 2) (Cons (inc 3) (map inc [])))\pause{}
  Cons (inc 1) (Cons (inc 2) (Cons (inc 3) Nil))\pause{}
  Cons (inc 1) (Cons (inc 2) (Cons 4 Nil))\pause{}
  Cons (inc 1) (Cons 3 (Cons 4 Nil))\pause{}
  Cons 2 (Cons 3 (Cons 4 Nil))\color{gray}-- or [2, 3, 4]
  \end{Verbatim}
\end{frame}

\begin{frame}[c, fragile]
  \frametitle{Going further}
  We can define arbitrary nested structures in this way:\pause{}

  \begin{Verbatim}[commandchars=\\\{\}]
  data FSEntry = \color{gray}-- file system entry\pause{}
    File String String | \color{gray}-- name, extension\pause{}
    Executable String | \color{gray}-- name\pause{}
    Folder String [FSEntry] | \pause{}
    Archive String String [FSEntry] 
  \end{Verbatim}
  \pause{}
  
  \medskip

  Such structures are very common: trees, semi-structured data (XML, JSON,
  etc), expression trees, and many more, can be represented this way very
  naturally.\pause{} However, working with {\em these\/} is much less easy.
\end{frame}

\begin{frame}[c, fragile]
  \frametitle{Why this is awful}
  Let's suppose we wanted a function which told us how deeply-nested our file
  system is:\pause{}
  
  \begin{Verbatim}[commandchars=\\\{\}]
  depth :: FSEntry -> Integer \pause{}
  depth File _ _ = 0 \pause{}
  depth Executable _ = 0 \pause{}
  depth Folder _ entries = 1 + max (map depth entries) \pause{}
  depth Archive _ _ entries = 1 + max (map depth entries)
  \end{Verbatim}
  \pause{}

  This is already looking bad. But it could be even
  worse\ldots
\end{frame}

\begin{frame}[c, fragile]
  \frametitle{Why this awful, part 2}
  Suppose we wanted a list of every file with a {\tt .c} or {\tt .h} extension:\pause{}

  \begin{Verbatim}[commandchars=\\\{\}]
  findCSource :: FSEntry -> [FSEntry]\pause{}
  findCSource File name "c" = [File name "c"]
  findCSource File name "h" = [File name "h"]\pause{}
  findCSource File _ _ = []\pause{}
  findCSource Executable _ = []\pause{}
  findCSource Folder _ es = concat (map findCSource es)\pause{}
  findCSource Archive _ _ es = concat (map findCSource es)
  \end{Verbatim}
  \pause{}
  That is absolutely {\em gross}.\pause{} Now, imagine having to write `unpack
  all archives, and place them in their own folders, with the same name and {\tt
  "unpacked"} appended'\ldots
\end{frame}

\begin{frame}[c]
  \frametitle{Enumerating our gripes}
  \pause{}
  \begin{itemize}
    \item Conflates {\em structure\/} (how the data is arranged) with {\em
      content\/} (what the data is)\pause{}
    \item Difficult and counter-intuitive to write\pause{}
    \item Brittle and hard to extend\pause{}
    \item Tedious and repetitive\pause{}
  \end{itemize}
  \medskip
  These are the sorts of problems `object-oriented' programming should concern
  itself with. We, as functional programmers, should (and {\em can\/}) do better than this!
\end{frame}

\section{Recursion schemes}

\begin{frame}[c]
  \frametitle{Recursion schemes}
  \pause{}
  \begin{itemize}
    \item First introduced in a 1991 paper by Meijer, Fokkinga and Paterson,
      titled {\em Functional Programming with Bananas, Lenses, Envelopes and
      Barbed Wire\/}\pause{}
    \item Describes a set of simple functions which can arbitrarily query, tear
      down, and build up recursive data types\pause{}
    \item Separates structure from content, allowing easy definition and
      extension\pause{}
    \item Have fancy Greek names (but aren't really all that scary)\pause{}
    \item Not widely known (even among functional programming afficionados) or
      implemented (even in Haskell!)\pause{}
  \end{itemize}

  \medskip

  Meijer, Fokkinga and Paterson called these functions {\em morphisms}.\pause{}
  Let's give them a look\ldots
\end{frame}

\begin{frame}[c, fragile]
  \frametitle{First of all}
  To make use of recursion schemes, we have to turn our nested structure into a
  functor (and give it a type parameter):\pause{}

  \begin{Verbatim}[commandchars=\\\{\}]
    data FSEntry a = 
      File String String |
      Executable String |
      Folder String [a] |
      Archive String String [a]

    instance Functor FSEntry where
      map f (File n e) = File n e
      map f (Executable n) = Executable n
      map f (Folder n es) = Folder n (map f es)
      map f (Archive n e es) = Archive n e (map f es)
  \end{Verbatim}
  \pause{}
  The functor definition is simple enough that it can be auto-derived by the
  compiler. At least one compiler actually does this (GHC for Haskell).
\end{frame}

\begin{frame}[c, fragile]
  \frametitle{A slight typing problem}

  The old {\tt FSEntry} type was {\em uniform\/}:\pause{}

  \begin{Verbatim}[commandchars=\\\{\}]
  file = File "foo" "txt" \color{gray}-- file :: FSEntry
  trash = Executable "Edge" \color{gray}-- trash :: FSEntry
  src = Folder "src" [(File "foo" "c"), 
    (Executable "foo")] \color{gray}-- src :: FSEntry
  rar = Archive "src" "rar" [src] \color{gray}-- rar :: FSEntry
  \end{Verbatim}
  \pause{}

  The new {\tt FSEntry}, however, is not:\pause{}

  \begin{Verbatim}[commandchars=\\\{\}]
  file = File "foo" "txt" \color{gray}-- file :: FSEntry String
  trash = Executable "Edge" \color{gray}-- trash :: FSEntry String
  src = Folder "src" [(File "foo" "c"), 
    (Executable "foo")] \color{gray}-- src :: FSEntry (FSEntry String)
  rar = Archive "src" "rar" 
    [src] \color{gray}-- rar :: FSEntry (FSEntry (FSEntry String))
\end{Verbatim}
\pause{}
This is a nuisance.
\end{frame}

\begin{frame}[c, fragile]
  \frametitle{Tying the knot}
  We really want to have some way of saying `this type is an arbitrarily-nested
  {\tt FSEntry}', kind of like this:\pause{}

  \begin{Verbatim}[commandchars=\\\{\}]
  type NestedFSEntry = FSEntry (FSEntry (FSEntry \ldots))
  \end{Verbatim}
  \pause{}

  This appears impossible. However, it can be done with a bit of profitable
  cheating:\pause{}

  \begin{Verbatim}[commandchars=\\\{\}]
  data Knot f = Tie \{ untie :: f (Knot f) \}
  
  file = Tie (File "foo" "txt") \color{gray}-- file :: Knot FSEntry
  src = Tie (Folder "src" [(File "foo" "c"), 
    (Executable "foo")]) \color{gray}-- src :: Knot FSEntry
  rar = Tie (Archive "src" "rar"
    [src]) \color{gray}-- rar :: Knot FSEntry
  \end{Verbatim}

  \pause{}
  This is called the {\em fixed point\/} of the {\tt FSEntry} type, which is the
  same as our earlier {\tt NestedFSEntry}.
\end{frame}

\begin{frame}[c, fragile]
  \frametitle{A little helper}
  To make our next few steps a bit easier, we're going to define a `pipeline'
  function:\pause{}

  \begin{Verbatim}[commandchars=\\\{\}]
  \color{gray}-- >>> is pronounced `then'
  >>> :: (a -> b) -> (b -> c) -> (a -> c)
  f >>> g = g \circ f \color{gray}-- \circ is function composition
  \pause{}
  f :: Integer -> Integer
  f = (+ 1) >>> (* 2)
  \pause{}
  answer = f 3 \color{gray}-- answer == 8
  \end{Verbatim}
  
\end{frame}

\begin{frame}[c]
  \frametitle{Separating structure from content}
  One of the biggest annoyances of our previous scheme is all the boilerplate
  dealing with structure --- let's be rid of it, once and for all.\pause{} As
  we're dealing with tree-like structures, there's two ways we can process
  them:\pause{}
  
  \medskip

  \begin{description}[Bottom-up:]
    \item[Bottom-up:] Descendants before ancestors
    \item[Top-down:] Ancestors before descendants
  \end{description}
  \pause{}
  
  \medskip

  This is where our {\tt Functor} instance can really shine --- we can use it to
  automate the `process descendants' step, without worrying about our structure
  or breaking it (due to the functor law).\pause{} We just need to provide a
  {\em local\/} processing function, which deals with our content.
\end{frame}

\begin{frame}[c, fragile]
  \frametitle{Bottom-up processing}
  To process a recursive data structure {\em bottom-up\/} using the processing
  function {\tt f}, we need to take the following steps:\pause{}

  \begin{enumerate}
    \item Untie the {\tt Knot}\pause{}
    \item Process descendants using {\tt map f}\pause{}
    \item Re-tie the {\tt Knot}\pause{}
    \item Process the ancestor using {\tt f}\pause{}
  \end{enumerate}

  In code terms:\pause{}

  \begin{Verbatim}[fontsize=\footnotesize,commandchars=\\\{\}]
  bottomUp :: Functor a => (Knot a -> Knot a) -> Knot a -> Knot a
  bottomUp f = untie >>> map (bottomUp f) >>> Tie >>> f 
  \end{Verbatim}
  \pause{}

  {\em Note:\/} {\tt bottomUp} absolutely and totally does not care what we tied
  into a {\tt Knot}. Furthermore, {\tt f} doesn't need to care about the
  structure anymore.
\end{frame}

\begin{frame}[c, fragile]
  \frametitle{Top-down processing}
  To process a recursive data structure {\em top-down\/} using the processing
  function {\tt f}, we need to take the following steps:\pause{}

  \begin{enumerate}
    \item Process the ancestor using {\tt f}\pause{} 
    \item Untie the {\tt Knot}\pause{}
    \item Process descendants using {\tt map f}\pause{}
    \item Re-tie the {\tt Knot}\pause{}
  \end{enumerate}

  In code terms:\pause{}

  \begin{Verbatim}[fontsize=\footnotesize,commandchars=\\\{\}]
  topDown :: Functor a => (Knot a -> Knot a) -> Knot a -> Knot a
  topDown f = f >>> untie >>> map (topDown f) >>> Tie 
  \end{Verbatim}
  \pause{}

  {\em Note:\/} {\tt topDown} absolutely and totally does not care what we tied
  into a {\tt Knot}. Furthermore, {\tt f} doesn't need to care about the
  structure anymore.
\end{frame}

\begin{frame}[c, fragile]
  \frametitle{Slipping the {\tt Knot}}
  Unfortunately, our separation of structure and content is not complete ---
  we're still tied (hurr hurr) to returning a {\tt Knot}, which is not enough to
  implement anything (too) useful.\pause{} What if we tried to `slip the {\tt
  Knot}' by `cleverly' forgetting to re-tie it?\pause{}

  \begin{Verbatim}[commandchars=\\\{\}]
  \color{gray}-- what would the type of this possibly be?
  mystery f = untie >>> map (mystery f) >>> f\pause{}

  \color{gray}-- mystery :: Functor f => (f a -> a) -> Knot f -> a
  \end{Verbatim}
  \pause{}

  Now, the separation is complete. Let's write some code!
\end{frame}

\begin{frame}[c, fragile]
  \frametitle{Revisiting {\tt depth}}
  \pause{}
  \begin{Verbatim}[commandchars=\\\{\}]
  countDepth :: FSEntry Int -> Int
  countDepth File _ _ = 0
  countDepth Executable _ = 0
  countDepth Folder _ es = 1 + max es
  countDepth Executable _ es = 1 + max es
  \pause{}
  depth :: Knot FSEntry -> Int
  depth = mystery countDepth
  \end{Verbatim}
  \pause{}

  \medskip

  {\tt countDepth} doesn't have to care about structure, while {\tt mystery}
  doesn't have to care about content. Success!
\end{frame}

\begin{frame}[c, fragile]
  \frametitle{Revisiting {\tt findCSource}}
  \pause{}
  \begin{Verbatim}[commandchars=\\\{\}]
  getCSource :: FSEntry String -> [FSEntry String]
  getCSource File n "c" = [File name "c"]
  getCSource File n "h" = [File name "h"]
  getCSource File _ _  = []
  getCSource Executable _ = []
  getCSource Folder _ es = concat es
  getCSource Archive _ _ es = concat es
  \pause{}
  findCSource :: Knot FSEntry -> [FSEntry]
  findCSource = mystery getCSource
  \end{Verbatim}
  \pause{}
  
  \medskip

  Woo-hoo!
\end{frame}

\begin{frame}[c]
  \frametitle{What you might be thinking right now}
  \begin{center}
    \includegraphics[scale=0.75]{img/what-kind-of-sorcery-is-this.pdf}
    \pause{}
    \medskip
    
    I assure you, it gets better!
  \end{center}
\end{frame}

\begin{frame}[c, fragile]
  \frametitle{Cleaning up our terminology}

  {\tt mystery} is a pretty silly name to give something so useful, and {\tt
  (f a -> a)} is really hard to pronounce. Let's name them sensibly:\pause{}

  \begin{Verbatim}[commandchars=\\\{\}]
  type Algebra f a = f a -> a

  \color{gray}-- the humble catamorphism, at last
  cata :: Functor f => Algebra f a -> Knot f -> a
  cata f = untie >>> map (cata f) >>> f
  \end{Verbatim}
  \pause{}

  The names seem a bit odd at first, but there are reasons for them:\pause{}
  
  \begin{description}[Catamorphism:]
    \item[Algebra:] Arabic root {\em jabr}, which means
      `restoration, reunion' --- an {\em algebra\/} `reunites' an {\tt f a} (a
      container of {\tt a}s) back into a single {\tt a}.\pause{}
    \item[Catamorphism:] Greek root {\em kata\/} (like
      `catastrophe'), which means `downwards, into, collapse' --- a {\em
      catamorphism\/} `collapses' a nested structure of values into a single
      value.
  \end{description}
\end{frame}

\begin{frame}[c, fragile]
  \frametitle{Extending to logical conclusions}
  We just managed to decouple structure from content for {\em bottom-up\/}
  traversals. But what if we tried to do the same for top-down ones?\pause{}

  \begin{Verbatim}[commandchars=\\\{\}]
  \color{gray}-- a reminder
  topDown f = f >>> untie >>> map (topDown f) >>> Tie
  \pause{}
  \color{gray}-- what is the type of this?
  wtf f = f >>> map (wtf f) >>> Tie\pause{}
  \color{gray}-- wtf :: (Functor f) => (a -> f a) -> a -> Knot f
  \end{Verbatim}
  \pause{}
  
  \medskip

  Seem familiar?
\end{frame}

\begin{frame}[fragile, c]
  \frametitle{Wtf is up with {\tt wtf}?}

  Consider the type signatures of {\tt cata} versus {\tt wtf}:\pause{}

  \begin{description}
    \item[{\tt cata}:] Takes an algebra and a nested structure, and `tears it
      down' into a single value \pause{}
    \item[{\tt wtf}:] Takes a `backwards-algebra' and a value, and `builds it
      up' into a nested structure\pause{}
  \end{description}

  Again, sensible naming is in order:\pause{}

  \begin{Verbatim}[commandchars=\\\{\}]
  type Coalgebra f a = a -> f a

  \color{gray}-- meet the anamorphism (from Greek root for `build')
  ana :: Functor f => Coalgebra f a -> a -> Knot f
  ana f = f >>> map (ana f) >>> Tie 
  \end{Verbatim}

  \pause{}
  Thanks to recursion schemes, we can now {\em build\/} nested structures up
  based on local expansions.
\end{frame}

\begin{frame}[c]
  \frametitle{Why recursion schemes are amazing}
  \pause{}
  \begin{itemize}
    \item Full separation of structure and content\pause{}
    \item Easy to modify, simpler to write\pause{}
    \item Formal guarantees of correct behaviour\pause{}
  \end{itemize}
  
  \medskip

  {\em All this\/} is possible because of the wonderful {\tt Functor}!
\end{frame}

\begin{frame}[c]
  \frametitle{Going further}
  \pause{}
  \begin{itemize}
    \item Context-sensitive construction and teardown ({\em paramorphisms\/} and
      {\em apomorphisms\/})\pause{}
    \item Processing via intermediate structures, generalization and
      simplification of divide-and-conquer ({\em hylomorphisms\/})\pause{}
    \item Generalize more expressive techniques (for example, trampolining with
      {\em zygomorphisms\/} and dynamic programming with {\em histomorphisms\/})\pause{}
    \item Processing {\em infinite\/} structures (yes, this is
        possible!)\pause{} 
    \end{itemize}

    \medskip

    But ultimately, this is {\em freedom from boilerplate}, {\em freedom from
      drudgery}, and ultimately, {\em freedom from structural
    processing}.\pause{}

    \medskip

    Still don't know how to used functor?
  \end{frame}

\section{Questions}

\begin{frame}[fragile, c]
  \frametitle{Questions?}
  \begin{center}
  \includegraphics[scale=0.27]{img/questions.pdf}
\end{center}
\end{frame}

\end{document}

